package leetcode.binarysearch;

import java.util.Arrays;
import java.util.Map;

public class Lc2300 {

    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        Arrays.sort(potions);
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int idx = binarySearch(potions, 0, m - 1, spells[i], success, m);
            ans[i] = m - idx;
        }
        return ans;
    }

    private int binarySearch(int[] potions, int l, int r, long spell, long success, int m) {
        if (l > r) return m;
        int mid = (l + r) / 2;
        int ret = m;
        if (potions[mid] * spell >= success) {
            ret = mid;
            int item = binarySearch(potions, l, mid - 1, spell, success, m);
            ret = Math.min(ret, item);
        } else {
            ret = binarySearch(potions, mid + 1, r, spell, success, m);
        }
        return ret;
    }


    public static void main(String[] args) {
        Lc2300 lc2300 = new Lc2300();
        int[] sp = {5,1,3};
        int[] p = {1,2,3,4,5};
        int su = 7;
        Arrays.stream(lc2300.successfulPairs(sp, p, su)).forEach(System.out::println);
    }
}
